计蒜客【NOIP2018模拟3】手拉手 <概率DP>

Problem

【NOIP2018模拟3】手拉手

Description

小 P 是个幼儿园老师。有一天，他组织个小朋友玩游戏。游戏开始时，每个小朋友伸出两只手，没有手相互拉在一起。每次，小 P 等概率随机挑选两只空着的手，让这两只手拉在一起。小 P 一直重复这个操作，直到所有的手都拉在一起。小 P 在成为幼儿园老师之前是个数学专业的博士。因此，他想知道，当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少？其中，我们规定，一个小朋友左手拉右手的情况也形成一个圈。
由于小 P 忙着和小朋友们玩游戏，他找到了聪明的你，希望你能帮他解决这个问题。

Input

输入数据仅一行，包含一个正整数，表示小朋友的数量。

Output

输出文件仅一行，包含一个实数，表示当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少。输出和标准答案的绝对误差不能超过。

Sample Input

Input #1

Input #2

Sample Output

Output #1

1	1.333333333

Output #2

1	7.889510292

Hint

Explanation #1
小 P 组织个小朋友玩游戏，我们称他们为小 A 和小 B。小 A 的左手等概率和小 A 的右手、小 B 的左手、小 B 的右手拉在一起，每一种情况的概率均为。若小 A 的左右手拉起来，那么最终会形成个圈，因为小 B 也必然左右手拉住。若小 A 的左手和小 B 的任意一只手拉起来，那么最终会形成一个圈，因为小 A 的右手必然和小 B 的另一只手拉住。那么，根据期望的公式，小 A 和小 B 拉成的圈个数的期望为

Constraint

对于的数据：。
对于的数据：。
对于的数据：。
对于的数据：。

Source

计蒜客 NOIP 提高组模拟竞赛第二试

标签：概率DP

Solution

用表示个点由上面的方法连边后期望下的环数。
考虑由个点的图如何变成由个点的图。可以将第个点加入到任意一条边中间，即把边拆断，用这个点分别连向原来这条边连接的两个点。原来有条边，而左右手有区别，所以有种加入的方案，而这样是不会产生新环的。还可以让第个点单独组成自环，共种方案，会产生个新环。于是加入第个点时，有的概率产生一个新环。因此有。
由此，我们可以，解决的部分分。

对于的部分，我们将递推式化为和式后化简。

上式中运用了调和级数，其中为欧拉常数，其约等于。而在的情况下我们可以将这个近似值作为答案。由此可以解得结果。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
const dnt C = 0.57721566490153286060651209;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int main() {
    dnt n; read(n);
    if (n <= MAX_N) {
        dnt sum = 0;
        for (dnt i = 1; i <= n; i++)
            sum += 1/(2*i-1);
        printf("%.9lf\n", sum);
    } else printf("%.9lf\n", log(n)/2+C/2+log(2));
    return 0;
}